import java.util.ArrayList;
import java.util.List;

/**
 * 331. 验证二叉树的前序序列化
 * https://leetcode-cn.com/problems/verify-preorder-serialization-of-a-binary-tree/
 */
public class Solutions_331 {
    public static void main(String[] args) {
        String str1 = "9,3,4,#,#,1,#,#,2,#,6,#,#";  // output: true
        String str2 = "1,#";  // output: false
        String str3 = "9,#,#,1";  // output: false

        List<String> inputs = new ArrayList<>();
        inputs.add(str1);
        inputs.add(str2);
        inputs.add(str3);

        for (String input : inputs) {
            boolean result = isValidSerialization(input);
            System.out.println(result);
        }
    }

    /**
     * 解题思路：利用树的前序遍历（根左右）性质
     * 以 "2,#,6,#,#" 为例
     *    2
     *   / \       两个空节点可以抵消一个非空节点
     *  #  6       非空节点被抵消后，产生一个新的空节点
     *    / \      若非空节点无法被抵消，即后续没有两个或两个以上的非空节点存在，验证失败
     *   #  #
     */
    public static boolean isValidSerialization(String preorder) {
        String[] arr = preorder.split(",");
        // 记录空节点的数量
        int cnt = 0;
        // 倒序循环
        for (int i = arr.length - 1; i >= 0; i--) {
            String str = arr[i];
            if (str.charAt(0) == '#') {
                cnt ++;
            } else {
                cnt -= 2;
                if (cnt < 0) {
                    return false;
                }
                cnt += 1;
            }
        }
        // 最终的根节点，被化简为空节点
        return cnt == 1;
    }
}
